import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Stack;

public class Solution {
    //给定一个链表，请判断该链表是否为回文结构。
    //回文是指该字符串正序逆序完全一致。
   public class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
      this.val = val;
    }
  }
  //方法一
    public boolean isPail (ListNode head) {

       if(head.next == null || head.next == null){
           return true;
       }
       ListNode mid = getMid(head);
       ListNode reversedSecondHalf = reverse(mid.next);
       return isSame(head,reversedSecondHalf);
    }
    //1.先找到中间位置
    public ListNode getMid(ListNode head){
       ListNode fast = head;
       ListNode slow = head;
       while(fast != null && fast.next != null){
           fast = fast.next.next;
           slow = slow.next;
       }
       return slow;
    }
    //2.翻转链表
    public ListNode reverse(ListNode head){
       ListNode prev = null;
       ListNode curr = head;
       while(curr!= null){
           ListNode nextTemp = curr.next;
           curr.next = prev;
           prev = curr;
           curr = nextTemp;
       }
       return prev;
    }
    //3.比较是否相等
    public boolean isSame(ListNode head1,ListNode head2){

        while (head2 != null) {
            if (head1.val != head2.val) {
                return false;
            }
            head1 = head1.next;
            head2 = head2.next;
        }
        return true;
    }

    //方法二
    public class Solution2 {
        public boolean isPail (ListNode head) {
            ArrayList<Integer> nums = new ArrayList();
            //将链表元素取出一次放入数组
            while(head != null){
                nums.add(head.val);
                head = head.next;
            }
            ArrayList<Integer> temp = new ArrayList();
            temp = (ArrayList<Integer>) nums.clone();
            //准备一个数组承接翻转之后的数组
            Collections.reverse(temp);
            for(int i = 0; i < nums.size(); i++){
                int x = nums.get(i);
                int y = temp.get(i);
                //正向遍历与反向遍历相同
                if(x != y)
                    return false;
            }
            return true;
        }
    }
    public class Solution3{
       public boolean isPail(ListNode head){
           ArrayList<Integer> nums = new ArrayList<>();
           while(head != null){
               nums.add(head.val);
               head = head.next;
           }
           ArrayList<Integer> tmp = new ArrayList<>();
           tmp = (ArrayList<Integer>) nums.clone();
           Collections.reverse(tmp);
           for(int i = 0; i < nums.size();i++){
               int x = nums.get(i);
               int y = tmp.get(i);
               if( x != y)
                   return false;
           }
           return true;
       }
    }


}
